{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #判断对称二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkSymmetricTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断对称二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>请设计一个函数判断一棵二叉树是否 <strong>轴对称</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1694689008-JaaRdV-%E8%BD%B4%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%911.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [6,7,7,8,9,9,8]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>从图中可看出树是轴对称的。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1694689054-vENzHe-%E8%BD%B4%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%912.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,2,null,3,null,3]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>从图中可看出最后一层的节点不对称。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><code>0 &lt;= 节点个数 &lt;= 1000</code></p>\n",
    "\n",
    "<p>注意：本题与主站 101 题相同：<a href=\"https://leetcode-cn.com/problems/symmetric-tree/\">https://leetcode-cn.com/problems/symmetric-tree/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [dui-cheng-de-er-cha-shu-lcof](https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [dui-cheng-de-er-cha-shu-lcof](https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,7,7,8,9,9,8]', '[6,7,7,8,null,8,null]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def compare(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:\n",
    "        if not left and not right:\n",
    "            return True\n",
    "        elif left and not right:\n",
    "            return False\n",
    "        elif right and not left:\n",
    "            return False\n",
    "        elif left.val != right.val:\n",
    "            return False\n",
    "        else:\n",
    "            return self.compare(left.left, right.right) and self.compare(left.right, right.left)\n",
    "\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return self.compare(root.left, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: TreeNode) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R: return True\n",
    "            if not L or not R or L.val != R.val: return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "\n",
    "        return not root or recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R: return True\n",
    "            if not L or not R or L.val != R.val: return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "\n",
    "        return not root or recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "        \n",
    "        def recur(A, B):\n",
    "            if not A and not B: return True\n",
    "            if not A or not B: return False\n",
    "            if A.val == B.val: return recur(A.left, B.right) and recur(A.right, B.left)\n",
    "            else: return False\n",
    "\n",
    "        return recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "      def dfs(left, right):\n",
    "        if left and right and left.val==right.val:\n",
    "          left_same= dfs(left.left, right.right)\n",
    "          return left_same and dfs(left.right,right.left)\n",
    "        elif not left and not right:\n",
    "          return True\n",
    "        else:\n",
    "          return False\n",
    "      return not root or dfs(root.left,root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(l,r):\n",
    "            if not l and not r:\n",
    "                return True\n",
    "            if not l or not r or l.val != r.val:\n",
    "                return False\n",
    "            return  recur(l.left, r.right) and recur(l.right, r.left)\n",
    "        return not root or recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "#         def in_order(root, res=None):\n",
    "#             \"\"\"中序遍历\"\"\"\n",
    "#             if root is None:\n",
    "#                 return\n",
    "#             if res is None:\n",
    "#                 res = []\n",
    "\n",
    "#             # 访问优先级：左子树 -> 根节点 -> 右子树\n",
    "#             in_order(root.left, res)\n",
    "#             res.append(root.val)\n",
    "#             in_order(root.right, res)\n",
    "#             return res\n",
    "#         res = in_order(root)\n",
    "#         n = len(res)//2\n",
    "#         print(res, n, res[n-1::-1], res[n+1:])\n",
    "\n",
    "#         if res[n-1::-1] == res[n+1:]:\n",
    "#             return True\n",
    "#         return False\n",
    "\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: TreeNode) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R: return True\n",
    "            if not L or not R or L.val != R.val: return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "\n",
    "        return not root or recur(root.left, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def check(cur_1, cur_2):\n",
    "            nonlocal res\n",
    "            if res:\n",
    "                if not cur_1 and not cur_2:\n",
    "                    return\n",
    "                if not cur_1 or not cur_2 or cur_1.val != cur_2.val:\n",
    "                    res = False\n",
    "                    return\n",
    "                check(cur_1.left, cur_2.right)\n",
    "                check(cur_1.right, cur_2.left)\n",
    "            \n",
    "        \n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        res = True\n",
    "        check(root.left, root.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        q = [root]\n",
    "        while q:\n",
    "            i, j = 0, len(q)-1\n",
    "            while i < j:\n",
    "                x = q[i].val if q[i] else -65536\n",
    "                y = q[j].val if q[j] else -65536\n",
    "                if x != y:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            tmp = []\n",
    "            for node in q:\n",
    "                if node:\n",
    "                    tmp.append(node.left)\n",
    "                    tmp.append(node.right)\n",
    "            q = tmp\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def isMirror(left, right):\n",
    "            # 如果两个节点都为空，它们是对称的\n",
    "            if not left and not right:\n",
    "                return True\n",
    "            # 如果其中一个节点为空，或者节点的值不相等，它们不是对称的\n",
    "            if not left or not right or left.val != right.val:\n",
    "                return False\n",
    "            \n",
    "            # 递归检查左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点\n",
    "            return isMirror(left.left, right.right) and isMirror(left.right, right.left)\n",
    "        \n",
    "        # 如果根节点为空，它是对称的\n",
    "        if not root:\n",
    "            return True\n",
    "        # 调用辅助函数检查左子树和右子树是否对称\n",
    "        return isMirror(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L,R):\n",
    "            if not L and not R:return True\n",
    "            if not L or not R or L.val != R.val:return False\n",
    "            return recur(L.left,R.right) and recur(L.right,R.left)\n",
    "\n",
    "        return not root or recur(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def issys(A,B):\n",
    "            if not A and not B:\n",
    "                return True\n",
    "            elif A and B:\n",
    "                # print(1)\n",
    "                if A.val==B.val:\n",
    "                    # print(1)\n",
    "                    # print(A.left)\n",
    "                    return issys(A.left,B.right) and issys(A.right,B.left)\n",
    "                    # print(issys(A.left,B.right) and issys(A.right,B.left))\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "        if not root:\n",
    "            return True\n",
    "        return issys(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "        q1 = [root.left]\n",
    "        q2 = [root.right]\n",
    "\n",
    "        while q1 and q2:\n",
    "            n1 = q1.pop()\n",
    "            n2 = q2.pop()\n",
    "            if not n1 and not n2:\n",
    "                continue\n",
    "            if not n1 or not n2 or n1.val != n2.val:\n",
    "                return False\n",
    "            q1.append(n1.left)\n",
    "            q1.append(n1.right)\n",
    "            q2.append(n2.right)\n",
    "            q2.append(n2.left)\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: TreeNode) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R: return True\n",
    "            if not L or not R or L.val != R.val: return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "\n",
    "        return not root or recur(root.left, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def Checkpoint(L,R):\n",
    "            if not L and not R:\n",
    "                return True\n",
    "            elif not L or not R:\n",
    "                return False\n",
    "            elif L.val != R.val:\n",
    "                return False\n",
    "            else:\n",
    "                return Checkpoint(L.right,R.left) and Checkpoint(L.left,R.right)\n",
    "        if not root:\n",
    "            return True\n",
    "        return Checkpoint(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def panding(L,R):\n",
    "            if not L and not R:return True\n",
    "            if not L or not R or L.val!=R.val:return False\n",
    "            return panding(L.left,R.right) and panding(L.right,R.left)\n",
    "        return bool( not root) or panding(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L,R):\n",
    "            if not L and not R:return True\n",
    "            if not L or not R or L.val != R.val:return False\n",
    "            return recur(L.left,R.right) and recur(L.right,R.left)\n",
    "        return not root or recur(root.left,root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L,R):\n",
    "            if not L and not R:return True\n",
    "            if not L or not R or L.val!=R.val:return False\n",
    "            return recur(L.left,R.right) and recur(L.right,R.left)\n",
    "        return not root or recur(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        if not root:\n",
    "            return True\n",
    "        else:\n",
    "            return self.ccmp(root.left, root.right)\n",
    "\n",
    "    def ccmp(self,left: TreeNode,right: TreeNode) -> bool:\n",
    "        if not left and not right:\n",
    "            return True\n",
    "        elif not left or not right:\n",
    "            return False\n",
    "        elif left.val != right.val:\n",
    "            return False\n",
    "        else:\n",
    "            return self.ccmp(left.left,right.right) and self.ccmp(left.right,right.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L,R):\n",
    "            if not L and not R: return True\n",
    "            if not L or not R or L.val != R.val:return False\n",
    "            return recur(L.left,R.right) and recur(L.right,R.left)\n",
    "        return not root or recur(root.left,root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def isturn(A,B):\n",
    "            if (A and not B) or (not A and B): return False\n",
    "            if not A and not B: return True\n",
    "            if A.val != B.val: return False\n",
    "            return isturn(A.left,B.right) and isturn(A.right,B.left)\n",
    "\n",
    "        if not root or (not root.left and not root.right): return True\n",
    "        if root.left and root.right: return isturn(root.left,root.right)\n",
    "        else: return False\n",
    "\n",
    "            #     if (A and not B) or (not A and B): return False\n",
    "        #     if not A and not B: return True\n",
    "        #     if A.val != B.val: return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(A,B):\n",
    "            if A==B==None:\n",
    "                return True\n",
    "            if A and B and A.val==B.val:\n",
    "                return recur(A.left,B.right) and recur(A.right,B.left)\n",
    "            return False\n",
    "        if root is None:\n",
    "            return True  \n",
    "        return recur(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def check(root1, root2):\n",
    "            if not root1 and not root2:\n",
    "                return True\n",
    "            if not root1 or not root2 or root1.val != root2.val:\n",
    "                return False \n",
    "            return check(root1.left, root2.right) and check(root1.right, root2.left)\n",
    "        return check(root, root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "#看完代码随想录之后过来刷一下\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def check(left,right):\n",
    "            if right == None and left == None:\n",
    "                return True\n",
    "            if right == None or left == None:\n",
    "                return False\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            #到这里一定注意不能写这种，因为这里一返回就不再继续分析下面的情况了    \n",
    "            # if left.val == right.val:\n",
    "            #    return True    \n",
    "\n",
    "            #到这里说明这一层是没问题的，有问题的都被上面拦住了\n",
    "            #但是这一层的孩子的情况还不确定，所以继续向下判断\n",
    "            outside = check(left.left,right.right)\n",
    "            inside = check(left.right,right.left)\n",
    "            return inside and outside\n",
    "        \n",
    "        if not root:\n",
    "            return True\n",
    "        return check(root.left,root.right)\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root):\n",
    "        def recur(L, R):\n",
    "            if not L and not R:\n",
    "                return True\n",
    "            if not L or not R or L.val != R.val:\n",
    "                return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "        return not root or recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "        queue = deque()\n",
    "        queue.append(root.left)\n",
    "        queue.append(root.right)\n",
    "        while queue:\n",
    "            left = queue.popleft()\n",
    "            right = queue.popleft()\n",
    "            if not left and not right: continue\n",
    "            elif not left or not right or left.val != right.val: return False\n",
    "            queue.append(left.left)\n",
    "            queue.append(right.right)\n",
    "            queue.append(left.right)\n",
    "            queue.append(right.left)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def judge(A, B):\n",
    "            if not A and not B:return True\n",
    "            if A and B and A.val == B.val:\n",
    "                return judge(A.left, B.right) and judge(A.right, B.left)\n",
    "            return False\n",
    "\n",
    "        if not root:return True\n",
    "        return judge(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "        res, queue = [], collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                tmp.append(node.left.val if node.left else None)\n",
    "                tmp.append(node.right.val if node.right else None)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            if tmp[::-1] != tmp:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R: \n",
    "                return True\n",
    "            if not L or not R or L.val != R.val:\n",
    "                return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "        return not root or recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:return True\n",
    "        def recur(left,right):\n",
    "            if not left and not right:return True\n",
    "            if not left or not right or left.val != right.val:return False\n",
    "            return recur(left.left,right.right) and recur(left.right,right.left)\n",
    "        return recur(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def check(p,q):\n",
    "            if not p and not q:\n",
    "                return True\n",
    "            elif p and q:\n",
    "                return (p.val==q.val) and check(p.left,q.right) and check(p.right,q.left)\n",
    "            else:\n",
    "                return False\n",
    "        return check(root,root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R: return True\n",
    "            if not L or not R or L.val != R.val: return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "        return not root or recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        #result = []\n",
    "\n",
    "        def ismirror(node1,node2):\n",
    "            if node1 is None and node2 is None:\n",
    "                return True\n",
    "            if node1 is None or node2 is None:\n",
    "                return False\n",
    "\n",
    "            return( node1.val == node2.val) and ismirror(node1.left,node2.right) and ismirror(node1.right,node2.left)\n",
    "\n",
    "        return ismirror(root,root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return self.isSymmetricTree(root.left, root.right)\n",
    "\n",
    "    def isSymmetricTree(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:\n",
    "        if left is None and right is None:\n",
    "            return True\n",
    "        if left is None or right is None:\n",
    "            return False\n",
    "        return left.val == right.val and self.isSymmetricTree(left.left, right.right) and self.isSymmetricTree(left.right, right.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R: return True\n",
    "            if not L or not R or L.val != R.val: return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "            \n",
    "        return not root or recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: TreeNode) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R: return True\n",
    "            if not L or not R or L.val != R.val: return False\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "\n",
    "        return not root or recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "        if not root.left and not root.right: return True\n",
    "        elif not root.left or not root.right: return False\n",
    "        def recur(A, B):\n",
    "            if not A and not B: return True\n",
    "            if not A or not B or A.val != B.val: return False\n",
    "            return recur(A.left, B.right) and recur(A.right, B.left)\n",
    "        return recur(root.left, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def getRes(left, right):\n",
    "            if left == None and right == None:\n",
    "                return True\n",
    "            if (left != None and right == None) or (left == None and right!=None):\n",
    "                return False\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            \n",
    "            l = getRes(left.left, right.right)\n",
    "            r = getRes(left.right, right.left)\n",
    "\n",
    "            return l and r\n",
    "        \n",
    "        return getRes(root.left, root.right) if root!=None else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # if not root: return True\n",
    "        # queue = deque()\n",
    "        # queue.append(root.left)\n",
    "        # queue.append(root.right)\n",
    "        # while queue:\n",
    "        #     left = queue.popleft()\n",
    "        #     right = queue.popleft()\n",
    "        #     if not left and not right: continue\n",
    "        #     elif not left or not right or left.val != right.val: return False\n",
    "        #     queue.append(left.left)\n",
    "        #     queue.append(right.right)\n",
    "        #     queue.append(left.right)\n",
    "        #     queue.append(right.left)\n",
    "        # return True\n",
    "\n",
    "\n",
    "\n",
    "        def helper(left, right):\n",
    "            if not left and not right: return True\n",
    "            elif not left or not right or left.val != right.val: return False\n",
    "            return helper(left.left, right.right) and helper(left.right, right.left)\n",
    "        return helper(root.left, root.right) if root else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(L, R):\n",
    "            if not L and not R:\n",
    "                return True\n",
    "            if not L or not R or L.val != R.val:\n",
    "                return False\n",
    "            \n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "    \n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        return recur(root.left, root.right)\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def isSymmetric(A,B):\n",
    "            if not A and not B:return True\n",
    "            if A and B:\n",
    "                return A.val == B.val and isSymmetric(A.left,B.right) and isSymmetric(A.right,B.left)\n",
    "            return False\n",
    "\n",
    "        return isSymmetric(root,root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSame(self,root1, root2):\n",
    "        if not root1 and not root2:\n",
    "            return True\n",
    "        if root1 and root2:\n",
    "            if root1.val == root2.val:\n",
    "                return self.isSame(root1.left, root2.right) and self.isSame(root1.right, root2.left)\n",
    "        return False\n",
    "\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if not root.left and not root.right:\n",
    "            return True\n",
    "        if not root.left or not root.right or root.left.val != root.right.val:\n",
    "            return False\n",
    "        return self.isSame(root.left.left,root.right.right) and self.isSame(root.left.right,root.right.left)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:return True\n",
    "        def f(left,right):\n",
    "            if not left and not right:\n",
    "                return True\n",
    "            elif not left or not right or left.val != right.val:\n",
    "                return False\n",
    "            return f(left.left,right.right) and f(left.right,right.left)\n",
    "        return f(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def isMirror(t1, t2):\n",
    "            if not t1 and not t2: return True # 如果都为空，则是对称的\n",
    "            if not t1 or not t2: return False # 如果其中一个为空另一个不是，则不是对称的\n",
    "            if t2.val != t1.val:\n",
    "                return False\n",
    "            return isMirror(t1.right,t2.left) and isMirror(t1.left,t2.right)\n",
    "\n",
    "        return isMirror(root,root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def judge(A, B):\n",
    "            if not A and not B:return True\n",
    "            if A and B and A.val == B.val:\n",
    "                return judge(A.left, B.right) and judge(A.right, B.left)\n",
    "            return False\n",
    "\n",
    "        if not root:return True\n",
    "        return judge(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:return True\n",
    "        que = collections.deque()\n",
    "        que.append(root.left)\n",
    "        que.append(root.right)\n",
    "        while que:\n",
    "            node1 = que.popleft()\n",
    "            node2 = que.popleft()\n",
    "            if not node1 and not node2:continue\n",
    "            if not node1 or not node2 or node1.val != node2.val:\n",
    "                return False\n",
    "            que.append(node1.left)\n",
    "            que.append(node2.right)\n",
    "            que.append(node1.right)\n",
    "            que.append(node2.left)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "\n",
    "        def recur(L, R):\n",
    "            if not L and not R: return True\n",
    "            if not L or not R or L.val != R.val: return False\n",
    "\n",
    "            return recur(L.left, R.right) and recur(L.right, R.left)\n",
    "\n",
    "\n",
    "        return recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root: return True\n",
    "        if not root.left and not root.right: return True\n",
    "        elif not root.left or not root.right: return False\n",
    "        def recur(A, B):\n",
    "            if not A and not B: return True\n",
    "            if not A or not B or A.val != B.val: return False\n",
    "            return recur(A.left, B.right) and recur(A.right, B.left)\n",
    "        return recur(root.left, root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def check_sub_tree(node1,node2):\n",
    "            if node1 is None and node2 is None:\n",
    "                return True\n",
    "            elif node1 is None and node2 is not None:\n",
    "                return False\n",
    "            elif node1 is not None and node2 is None:\n",
    "                return False\n",
    "            else:\n",
    "                if node1.val == node2.val:\n",
    "                    return check_sub_tree(node1.left,node2.right) and check_sub_tree(node1.right,node2.left)\n",
    "                else:\n",
    "                    return False\n",
    "        if not root:\n",
    "            return True\n",
    "        return check_sub_tree(root.left,root.right)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        def isSym(left, right):\n",
    "            if not left and not right:\n",
    "                return True\n",
    "            if not left or not right:\n",
    "                return False\n",
    "            if left.val != right.val:\n",
    "                return False\n",
    "            return isSym(left.left, right.right) and isSym(left.right, right.left)\n",
    "\n",
    "        return isSym(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def check(p, q):\n",
    "            if not p and not q:\n",
    "                return True\n",
    "            if not p or not q:\n",
    "                return False\n",
    "            if p.val != q.val:\n",
    "                return False\n",
    "\n",
    "            return check(p.left, q.right) and check(p.right, q.left)\n",
    "\n",
    "        return not root or check(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "\n",
    "        # BFS\n",
    "        q = deque([root.left, root.right])\n",
    "        while q:\n",
    "            node1 = q.popleft()\n",
    "            node2 = q.popleft()\n",
    "            if node1 is None and node2 is None:\n",
    "                continue\n",
    "            elif (node1 is None or node2 is None) or (node1.val != node2.val):\n",
    "                return False\n",
    "            \n",
    "            q.append(node1.left)\n",
    "            q.append(node2.right)\n",
    "            q.append(node1.right)\n",
    "            q.append(node2.left)\n",
    "        return True\n",
    "\n",
    "        # # DFS\n",
    "        # def check(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:\n",
    "        #     if left is None and right is None:\n",
    "        #         return True\n",
    "        #     elif left is None or right is None:\n",
    "        #         return False\n",
    "            \n",
    "        #     if left.val != right.val:\n",
    "        #         return False\n",
    "            \n",
    "        #     return check(left.left, right.right) and check(left.right, right.left)\n",
    "\n",
    "        # return check(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        queue1 = deque()\n",
    "        queue2 = deque()\n",
    "        queue1.append(root.left)\n",
    "        queue2.append(root.right)\n",
    "        while len(queue1) is not 0:\n",
    "            temp_len = len(queue1)\n",
    "            for i in range(0,temp_len):\n",
    "                temp1 = queue1.popleft()\n",
    "                temp2 = queue2.popleft()\n",
    "                if temp1 is not None and temp2 is not None and temp1.val != temp2.val:\n",
    "                    return False\n",
    "                elif temp1 is not None and temp2 is None:\n",
    "                    return False\n",
    "                elif temp2 is not None and temp1 is None:\n",
    "                    return False\n",
    "                elif temp2 is None and temp1 is None:\n",
    "                    continue\n",
    "                else:\n",
    "                    queue1.append(temp1.left)\n",
    "                    queue2.append(temp2.right)\n",
    "                    queue1.append(temp1.right)\n",
    "                    queue2.append(temp2.left)\n",
    "        if len(queue2) is not 0:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        return self.compare(root.left, root.right)\n",
    "\n",
    "    def compare(self, left, right):\n",
    "        if left != None and right == None:\n",
    "            return False\n",
    "        elif left == None and right != None:\n",
    "            return False\n",
    "        elif left == None and right == None:\n",
    "            return True\n",
    "        elif left.val != right.val:\n",
    "            return False\n",
    "        \n",
    "        inside = self.compare(left.left, right.right)\n",
    "        outside = self.compare(left.right, right.left)\n",
    "        side = inside and outside\n",
    "        return side"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def help(a,b):\n",
    "            if not a and not b:return True\n",
    "            if not a or not b or a.val!=b.val:return False\n",
    "            return help(a.left,b.right) and help(a.right,b.left)\n",
    "\n",
    "        return not root or help(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "        return self.isSymmetric(root.left, root.right)\n",
    "\n",
    "\n",
    "\n",
    "    def isSymmetric(self, root_l, root_r):\n",
    "        if root_l is None and root_r is None:\n",
    "            return True\n",
    "        \n",
    "        if (root_l and root_r) and (root_l.val == root_r.val):\n",
    "            return self.isSymmetric(root_l.left, root_r.right) \\\n",
    "            and self.isSymmetric(root_l.right, root_r.left)\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def recur(a, b):\n",
    "            if not a and not b:\n",
    "                return True\n",
    "            if not a or not b:\n",
    "                return False\n",
    "            if a.val == b.val:\n",
    "                return recur(a.left, b.right) and recur(a.right, b.left)\n",
    "            return False\n",
    "\n",
    "        if not root: return True\n",
    "        return recur(root.left, root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        \n",
    "        def isSame(A,B):\n",
    "            if not A and not B:\n",
    "                return True\n",
    "            if (not A and B) or (not B and A):\n",
    "                return False\n",
    "            return A.val==B.val and isSame(A.right,B.left) and isSame(A.left,B.right)\n",
    "        \n",
    "        return isSame(root.left,root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return True\n",
    "\n",
    "        return self.isSymmetric(root.left, root.right)\n",
    "\n",
    "\n",
    "\n",
    "    def isSymmetric(self, root_l, root_r):\n",
    "        if root_l is None and root_r is None:\n",
    "            return True\n",
    "        \n",
    "        if (root_l and root_r) and (root_l.val == root_r.val):\n",
    "            return self.isSymmetric(root_l.left, root_r.right) \\\n",
    "            and self.isSymmetric(root_l.right, root_r.left)\n",
    "        \n",
    "        return False\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
